Control flow

In this notebook we introduce control flow tools that will allow us to write real world code used in simulations. As their name imply, these structures determine the paths that can be taken in a particular code. Let us start with the if/elif/else statement. The example below illustrates their general structure.

import random
x = random.random()
print("Random number picked in [0,1): ", x)
if x < 1/3:
    subinterval = "[0,1/3)"
elif x < 2/3:
    subinterval = "[1/3,2/3)"
else:
    subinterval = "[2/3,1)"
print("x belongs to " + subinterval)

The piece of code above uses the random module. This library contains implementations of pseudo-random number generators for several probability distributions. If you type random.random() in the interactive console, you will see that a number in the interval $[0,1)$ is printed to the screen. Thus, random.random() samples from the uniform probability distribution in $[0,1)$. In our code above, the number sampled is assigned to the variable x and a string is printed to the screen telling us what value x points to. What is done next depends on the value assigned to x. If the value sampled is less than $1/3$, the boolean expression x < 1/3 returns True and the command subinterval = "[0,1/3)" is executed. If the sampled number is greater than $1/3$, the interpreter ignores the assignment in the scope of the if statement and tests the condition on the elif statement. Therefore, if the variable x satisfies $\frac{1}{3}\leq$ x $< \frac{2}{3}$, the condition evaluated in the elif statement will return True and the line subinterval = "[1/3,2/3)" will be executed. On the other hand, if $\frac{2}{3}\leq$ x, both the if and elif conditions will be false and the line inside the scope of the else statement, subinterval = "[2/3,1)", will be executed. After this if/elif/else structure, a line telling us the interval x belongs to is printed. You should note that you can use as many elif statements as you want. Of course, you are not obliged to use neither elif nor else after an if statement: they are optional. The general formula for Python conditional statements is summarized below.

if boolean expression:
    block of code
elif another boolean expression:  #This is optional!
    another block of code
else:                             #This is optional too!
    yet another block of code

You can put these concepts in practice in the next exercises.

Exercise 1. Write a similar program to the example above.

This time, divide the interval $[0,1)$ in five subintervals. Use print statements to check your code.

Exercise 2. The module function.

Implement and plot the module function,

Exercise 3. The greatest of three numbers.

Write a function that takes in three numbers and returns the greatest one.

Exercise 4. Full solution to the quadratic equation.

The full solution to the quadratic equation $ax^2 + bx + c$ requires the use of complex numbers, so this is a great opportunity to introduce them. In Python the imaginary unit $i$ that squares to $-1$ is written as 1j. We can indeed see that this is so by typing the following code.

i = 1j
print("Type of i: ", type(i))
print("i squared: ", i**2)

Multiples of $i$ are obtained substituting the number 1 by the appropriate value. Thus, $3i$ becomes 3j. We can now move on to our problem. If you want more details about the complex type, you can always read the documentation.

In this problem, your task is to implement the solution to the quadratic equation considering separately the three cases: $\Delta > 0$, $\Delta < 0$ and $\Delta = 0$, where $\Delta = b^2 - 4ac$.

Now we get to the point where we will be able to write real world programs. The data structure that will allow us to do this is the for loop. With loops, we will be able to solve problems of arbitrary complexity. Up to this point, we have been writing programs that run in constant time. This means that the amount of time it will take to run them is bounded by their number of lines of code. Evidently this a problem, since as complexity grows we will have to write ever more lines of code. Clearly this task will quickly become impracticable. As an example, suppose we naively decide to compute the sum of the first $n$ natural numbers by adding them one by one. We would quickly be overwhelmed! A for loop does this trivially:

def sum_natural_numbers(n):
    """
    Sums the n first natural numbers

    n: last number in the sum
    """
    total_sum = 0
    for number in range(n+1):
        total_sum = total_sum + number
    return total_sum

The for loop above has been implemented with a range-type object. These objects are used in the following way.

range(start, stop, step)

We provide three arguments to range: a start point that defaults to $0$ if ommited; a stop point that has to be provided, since it has no default value; and a step size, which is how we will reach the stop point from the start point. The step size defaults to 1. Note that in the example we provided above, we have used exactly the default values for start and step, so we only cared to give the stop argument.

How does the sum_natural_numbers(n) function work? We initialize the total_sum variable, which points to the partial sums, to zero. After this, the for loop does the work for us. The variable number takes every single value from 0 to n in steps of 1 and adds it to total_sum. It is important to note that the command inside the for loop is only executed while number < n+1. That is, the value n+1 is itself excluded. That is why in our code above we computed the sum of the n first numbers with a range whose stop point is n+1. We can see all the elements generated by range by generating a list from it:

list(range_object)

Exercise 5. Compute sum of n first a-th powers of natural numbers.

Write code that implements the function $\text{Sum}(n,a) = \sum_{i=1}^n i^a$.

Exercise 6. Compute factorials.

Write a function that takes a natural number and returns its factorial.

Exercise 7. The Basel series.

It is said that Leonhard Euler proved the convergence of the Basel series in 1734. He showed that $\sum^\infty_{n=1} \frac{1}{n^2} = \frac{\pi^2}{6}$. Write a function that computes the sum of the first $n$ terms of the Basel series. Plot the partial sums versus $n$ with a horizontal line at $y = \frac{\pi^2}{6}$, so that it becomes evident that the Basel series is indeed converging.

Iterables

Loops are intimately related to iterables. Indeed we could tautologically say that iterables are data structures that can be looped or iterated over. We have been using them for a while now: whenever we plotted anything, we always had to create lists of x coordinates and y coordinates and pass them as arguments to plt.plot(). It is worth spending a little time in these data structures, since they are among Python's basic data types. They are the following.

1. Strings;
2. Lists;
3. Tuples;
4. Dictionaries.

Let us briefly review each of these types.

Strings

In Python, strings are of type str. They are created from characters enclosed between quotes (single or double). The most trivial use you can give them is simply to print text to the screen. For example,

print("hello world!")

prints this silly (albeit very canonical in computer science) message. There is a lot more to strings in Python though. Indeed, they are a nice oportunity to introduce some basic concepts related to object orientation. We can think of particular strings such as "hello world" as instances of a larger class of objects, in this case the class str. The advantage of thinking in these terms is that a class is a big bundle that includes not only the instances, but also functions that act on them. Such functions are called methods. For example, given any lower case string, we might want to get its upper case version. This is is easily accomplished with the str.upper() method.

myLowerCaseString = "hello world"
myUpperCaseString = myLowerCaseString.upper()
print(myUpperCaseString)

The pattern you see above, which is called dot notation, will repeat itself when using this object-oriented approach. The general recipe to apply the method myMethod to an instance myObject of a class is

myObject.myMethod(arguments)

Python provides several built-in string methods. As another example of introspection in Python, the methods available in a class can be seen with dir, such as in the example below.

dir(str)

In the next exercise you are invited to try a string method.

Exercise 8. Wiping out vowels from a string.

Define the function remove_vowels(aString) that takes in a string as input and returns another string that is equal to the first one except that with all vowels removed. Hint: use the str.replace() method. The empty string in Python is "" or ''.

Lists

We are going to view Python's list type as just that: a list of obects (although the concept of list can be made more precise in computer science). Python's lists have two important features: they are mutable and they can store objects of different types. By mutable we mean that we can "edit" the contents of a given list at any time. Let us try a small example.

myList = [1,2,"Hello World"]
print("This is my list: ", myList)
myList[0] = 0
print("This is my edited list: ", myList)
print("Length of myList: ", len(myList))

The above example illustrates the important points well. First, a list in Python is written with brackets. After initializing the list, we changed its zeroth entry. This is an important point to note: indexing in Python starts at zero. In the end we use the len() function to print the list's length, which is equal to the number of elements in the list. Also note that the list above contains objects of different types: int and str.

Just as with strings, Python has several built-in list methods that perform usual operations on lists. You will surely use them a lot.

Besides using lists to store data, we shall loop over them very often. Given any of the iterable types, we can do this with the following command.

for element in iterable:
    block of code

Another way to iterate over lists (and any other ordered iterable) is by indexing. Indeed given the iterable orderedIterable, we could write the following code to iterate over it.

for index in range(len(orderedIterable)):
    block of code

Let us try some exercises on lists now.

Exercise 9. Two ways to iterate.

Write two functions, print_iterable(anIterable) and print_by_index(orderedIterable). The first takes an iterable object and prints all its elements by the first method. The last one does the same, but using the second method. Test your functions with the string "hello world!" and the list [0,1,2,3,4,5,6,7,8,9].

Exercise 10. Indexing and slicing.

The purpose of this exercise is to get you familiar with the indexing possibilities offered by lists. A point to note is that although we use lists here, what you shall do in this exercise will also work with strings and tuples. Try to guess what should be the result of the following commands.

myList = list(range(20)) 
a = myList[-1]
b = myList[1:6] #This is a slice!
c = myList[-1]
d = myList[-14:-10]
e = myList[:10]
f = myList[-6:]
g = myList[-15:12]
h = myList[15:]
print("This is a: ", a)
print("This is b: ", b)
print("This is c: ", c)
print("This is d: ", d)
print("This is e: ", e)
print("This is f: ", f)
print("This is g: ", g)
print("This is h: ", h)

Exercise 11. Indexing and slicing embedded iterables.

In this exercise we analyze embedded iterables. For the sake of clarity, we consider lists whose elements are themselves lists (or some other kind of iterable like strings). Try to guess the output of the commands below.

myList = [[1,2,3], "hello world!", ['a','b',[4,5,6,7]]]
a = myList[0]
b = myList[0][1]
c = myList [-2]
d = myList[-2][-4]
e = myList[len(myList) - 1]
f = myList[len(myList) - 1][-1]
g = myList[len(myList) - 1][-1][2]
h = myList[len(myList) - 1][-1][:]
print("This is a: ", a)
print("This is b: ", b)
print("This is c: ", c)
print("This is d: ", d)
print("This is e: ", e)
print("This is f: ", f)
print("This is g: ", g)
print("This is h: ", h)

Exercise 12. Finding the divisors of a given number.

Write a function divisors(n) that takes as input a natural number and returns a list with all its positive divisors.

Exercise 13. Decimal number representation

In this exercise we will write code that decomposes decimal integers to their decimal power representation. Given an integer $z$ that has a $n$-length decimal power representation, say $z \simeq z_{n-1}...z_0$, with $z_i \in \{0,1,...,9\}$, its decimal power representation will be

Your program should take in an integer and return a string containing its decimal power representation.

Exercise 14. Build a list from a string.

Write a function build_list(aString) that takes in a string and returns a list with all the letters in the string. Hint: you may use a for loop, but there are other ways to do it.

Exercise 15. Find prime numbers.

Common sense tells us that as we take larger and larger natural numbers, the occurrence of primes becomes ever rarer. Let us investigate this proposition. Write a function that searches the first $n$ natural numbers for primes. Your function find_primes(n) should return a list with all the prime numbers $ \leq n$. Use your function to plot the proportion of natural numbers $\leq n$ that are primes. You should compare your plot to a plot of the function $f(n) = \frac{1}{\ln n}$ (see the prime number theorem).

Exercise 16. Binary search.

In this exercise we use binary search to find if an element is in a list. The algorithm works as follows: at each iteration, we divide the unsearched list in two halves and choose one of them to inspect. If the element we are searching for is found, the search stops and we return its index. If not, the search moves on to the unsearched half. Fill in the remaining steps below.

Tuples

The next iterable type in Python is the tuple type that consists, well, of tuples. They seem very similar to lists, so it is important to emphasize their differences. Just like strings, tuples are immutable. This means that once you have created a tuple object, you cannot change it anymore. This adds safety to your code when immutability is desired. Python's designers also had in their minds different uses for lists and tuples. Although not mandatory, lists should be homogeneous, whilst tuples should be heterogeneous. This means that each entry in a tuple ideally should have a different meaning. Think for example of polar coordinates $(r,\theta)$. The first entry of this tuple has a meaning (radial distance) that is different from the second one (angular position). Let us see some sample code that assigns a tuple to the variable myTuple.

myTuple = (1,2,3,4,5,6,7,8,9)
print(myTuple)

Exercise 17. Empty tuple and singleton.

Create tuples with zero and one element. Make sure you actually created a tuple by checking the types of your objects.

Dictionaries

Dictionaries (type dict) are an example of unordered iterable. In practice what this means is that dictionaries don't use the same number-based indexing system that we have seen in the other iterables. Instead, dictionaries can be viewed as maps that link keys to values. In order to access a particular value stored in a dictionary, we have to provide its corresponding key as an index. Hopefully, running the example below will make this explanation redundant.

myDict = {'a': 1, 'b': 2, 'c': 3}
print("myDict keys: ", myDict.keys())
print("myDict values: ", myDict.values())
print("Value associated to key 'b': ", myDict['b'])

Note in the code above the use of dictionary methods, myDict.keys() and myDict.values().

Exercise 18. Trying to access a dictionary's value by index.

As we have explained, dictionaries are unordered and therefore cannot be accessed by the usual range-of-numbers indexing like lists, for example. Using the myDict dictionary defined above, type myDict[0] and see what happens.

Some quick, important facts about dictionaries. First, the keys can only be immutable types. Thus, lists cannot be used as keys, for example. Strings, ints/floats and tuples, on the other hand, are perfectly acceptable keys. Second, as should be clear by now, dictionaries are constructed with a pair of braces; an empty pair of braces creates an empty dictionary. Third, we can always add key:value pairs by simply assigning the desired value to the new key. Again, an example should make these matters clear.

myEmptyDict = {}
print("This is an empty dictionary: ", myEmptyDict)
myEmptyDict['a'] = "First value added"
print("Key 'a' added: ", myEmptyDict)

Exercise 19. A dictionary of ASCII characters.

For quite a long time, the ASCII character encoding was the standard encoding system in many platforms. In this exercise we shall create a dictionary that encodes ASCII as follows. The dictionary's keys are the 128 characters encoded by ASCII. Its values are the binary encodings corresponding to each character. Fill the missing steps below.

Exercise 20. Caesar cipher.

The simplest type of encryption scheme is perhaps the Caesar cipher. The idea is to translate every character in the alphabet by a fixed value. If we translate every character by 2, for example, the resulting Caesar cipher maps $a \rightarrow c$, $b \rightarrow d$, ..., $x \rightarrow z$, $y \rightarrow a$, $z \rightarrow b$ and we perform all these substitutions in a given text to encode it. Write the function ceasar_cipher() that encodes a string. Do it by filling the code below, then test it in a string of your choice.

Global variables, scopes and referencing

At this point we are familiar with most of Python's basic structures, so this is a good moment to discuss scopes and namespaces again. The scope of variables has been briefly mentioned in the previous notebook. It is certainly a good idea to read about it a little more carefully now. Here, we want to introduce global variables. If you want a quick example that shows the difference between a local and a global variable, run the code below.

x = 42
def local_assignment():
    x = 3.14
    print("This is x inside of local_assignment(): ")
    print(x)
def global_assignment():
    global x
    x = 2.78
    print("This is x inside of global_assignment(): ")
    print(x)

print("This is x before calling any function:")
print(x)
print("Now I will call local_assignment():")
local_assignment()
print("Note that x in the global scope did not change:")
print(x)
print("Now I will call global_assignment():")
global_assignment()
print("Note that global_assignment() changed x! This is x in the global scope:")
print(x)

Hopefully, the example above made clear the point that variables defined inside of a function are local to the function's scope. If you wish to have different behaviour, you have to declare a global variable explicitly inside a function definition. A word of caution: although global variables can be pretty useful sometimes, their use is often disencouraged due to the extra difficulties they might introduce in the debugging process. Therefore, be parsimonious with their use.

Exercise 21. Swapping variables.

Suppose you have two scalar variables,a and b. One would commonly swap their values using a third auxiliary variable clike in the example below.

a = 1
b = 2
print("This is a before the swap: ", a)
print("This is b before the swap: ", b)
#Swapping
c = a
a = b
b = c
print("This is a after the swap: ", a)
print("This is b after the swap: ", b)

How would you write a function that swaps the values of any two variables?

Exercise 22. Coppying lists.

Copying lists in Python can be a tricky feat. This exercise aims to alert you to that. Suppose we want to copy a list from a variable a to a variable b. We might want to keep the list in a intact while performing some operations in b. As an example, suppose we want the list in b to contain the elements of a, but with the zeroth element changed. A naive first try would be the following.

a = [1,2,3]
b = a
print("This is a: ", a)
print("This is b: ", b)
b[0] = 10
print("This is a after the change in b: ", a)
print("This is b after the change in b: ", b)

Our code shows that we indeed changed b, but we also changed a! This is due to the fact that Python does not have variables strictly speaking, but names. When we execute the command b = a what we are actually doing is giving the list [1,2,3] another name, b. Thus, actions performed in b will be performed on the same list that the name a refers to. How would you solve this issue? Specifically, write a function that returns a copy of a list. Then test if you have a true copy by changing the zeroth element of the list returned by your function.

Recursion

We end this notebook with a brief discussion on recursion. We can view recursion as another kind of loop, one in which further values in the computation refer to previous values, so that the whole computation cascades to a defined set of primary cases. Thus recursion works by solving many smaller versions of the same problem. A classical example is the recursive computation of the factorial of a natural number. We write this example below.

def recursive_factorial(n):
    if n == 0:
        return 1
    else:
        return n*recursive_factorial(n-1)

This solution to the computation of factorials uses the trivial fact that $n! = n(n-1)!$. Note that to compute the factorial of $n$ we end up generating $n+1$ calls to recursive_factorial(). In this case it is not really a big deal, but in some cases, such as the computation of Fibonacci numbers, the number of recursive calls can grow quite overwhelmingly. We will investigate this in the next exercise.

Exercise 23. Computational complexity of Fibonacci sequence.

The Fibonacci sequence is an integer number sequence that relates to surprisingly disparate phenomena, ranging from pattern formation in nature to poetry optimization. The full Fibonacci sequence can be recursively generated as follows.

We want to investigate how fast the number of function calls grow when we recursively generate Fibonacci numbers. To achieve this, we shall use what is usually considered bad practice: a global variable. The global variable counter will count how many times the function fibonacci(n) is called. Fill the missing steps below.